#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType *elem;
    int TableLen;
}SSTable;
//初始化顺序表
void TableInit(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
void PrintTable(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
void swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
void BubbleSort(ElemType *A,int len)
{
    float flag;
    for (int i = 0; i < len-1; ++i) {   //控制的是有序数的数目
        flag = false;
        for (int j = len-1; j >i ; j--) {
            if(A[j-1]>A[j])
            {
                swap(A[j-1],A[j]);
                flag = true;
            }
        }
        if(false==flag)
            return;
    }
}
int Partition(ElemType *A,int low,int high)
{
    ElemType pivot=A[low];
    while (low<high)
    {
        while (low<high&&A[high]>pivot)
            high--;
        A[low]=A[high];
        while (low<high&&A[low]<pivot)
            low++;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}
void QuickSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int pivot_pos=Partition(A,low,high);
        QuickSort(A,low,pivot_pos-1);
        QuickSort(A,pivot_pos+1,high);
    }
}
/**
 *       j        i
 * 1 23 56 43    34 45
 * @return
 */
void InsertSort(ElemType *A,int len) {
    int i, j, insertVal;
    for (i = 1; i < len; i++){
        insertVal=A[i];
        //内层控制比较，j要大于等于0，同时A[j]大于insertVal时，A[j]的位置要往后覆盖
        for (j = i-1; j>=0&&A[j]>insertVal; j--) {
            A[j+1]=A[j];
        }
        A[j+1]=insertVal;
    }
}
//12 63 58 95 41 35 65  0 38 44
int main() {
    SSTable ST;
    TableInit(ST,10);
    ElemType A[10];
    for (int i = 0; i < ST.TableLen; ++i) {
        scanf("%d",&A[i]);
    }
    //冒泡排序
    memcpy(ST.elem,A, sizeof(A));
    BubbleSort(ST.elem,ST.TableLen);
    PrintTable(ST);
    //快速排序
    memcpy(ST.elem,A, sizeof(A));
    QuickSort(ST.elem,0,ST.TableLen-1);
    PrintTable(ST);
    //插入排序
    memcpy(ST.elem,A, sizeof(A));
    InsertSort(ST.elem,ST.TableLen);
    PrintTable(ST);
    return 0;
}
